package Bfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;


public class Bfs {

	Map<String, ArrayList<String>> map;
	
	public Bfs(Map<String, ArrayList<String>> map)
	{
		
		this.map=map;
	}
	
	public ArrayList<String> bfs(String start, String end)
	{
		ArrayList<String> path;
		ArrayList<String> new_path = new ArrayList<String>();
		
		String node;
		// maintain a queue of paths
		Queue queue = new LinkedList();
		// push the first path into the queue
		queue.add(new ArrayList<String>(Arrays.asList(start)));
		
		while(!queue.isEmpty()) 
		{
		   //get the first path from the queue
		   path= (ArrayList<String>) queue.poll();
		   //get the last node from the path
		   node=path.get(path.size()-1);

		   //path found
		   if(node.equals(end)) 
		   {
			   path.remove(0);
			   return path;
		   }
		   
		   //enumerate all adjacent nodes, construct a new path and push it into the queue
		   ArrayList<String> li = map.get(node);
		   for(String var: li )
		   {
			  
			  new_path = new ArrayList<String>(path);
			  new_path.add(var);
			  queue.add(new_path);
			  
		   }//for
		}//while
		
		return null;
		
	}//end of bfs
	
	
}
